def binary_search(array, x, start, end):
    if start == end - 1:
        if array[start] == x:
            return start
        elif array[end] == x:
            return end
        return -1
    middle_index = int((start + end) / 2)
    middle_value = array[middle_index]
    if middle_value == x:
        return middle_index
    if middle_value > x:
        return binary_search(array, x, start, middle_index - 1)
    else:
        return binary_search(array, x, middle_index + 1, end)


def test_binary_search():
    array = [1, 3, 4, 5, 7, 9, 8, 10]
    assert -1 == binary_search(array, 11, 0, len(array) - 1)
    index_of_5 = binary_search(array, 5 ,0, len(array) - 1)
    print("index_of_5 is ", index_of_5)
    assert 5 == array[index_of_5]
    assert 1 == array[binary_search(array, 1, 0, len(array) - 1)]
    assert 10 == array[binary_search(array, 10, 0, len(array) - 1)]
